module nxt.bit_traits;

static if (__VERSION__ >= 2083)
{
    version(LDC) static assert(!__traits(compiles, { enum _ = __traits(isZeroInit, T); }),
                               "Remove checks for __traits(compiles, { enum _ = __traits(isZeroInit, T); }) now that it compiles with LDC");
}

/** Get number of bits needed to represent the range (0 .. `length`-1).
 */
template bitsNeeded(size_t length)
{
    // TODO: optimize by removing need for a linear search
    static      if (length <= 2)   { enum bitsNeeded = 1; }
    else static if (length <= 4)   { enum bitsNeeded = 2; }
    else static if (length <= 8)   { enum bitsNeeded = 3; }
    else static if (length <= 16)  { enum bitsNeeded = 4; }
    else static if (length <= 32)  { enum bitsNeeded = 5; }
    else static if (length <= 64)  { enum bitsNeeded = 6; }
    else static if (length <= 128) { enum bitsNeeded = 7; }
    else static if (length <= 256) { enum bitsNeeded = 8; }
    else static if (length <= 512) { enum bitsNeeded = 9; }
    else                           { static assert(0, `Too large length`); }
}

/** Number of bits required to store a packed instance of `T`.
    See_Also: http://forum.dlang.org/thread/okonqhnxzqlqtxijxsfg@forum.dlang.org

    TODO: Extend to continuous version; use std.numeric.sumOfLog2s. Ask on
    StackExchange Computer Science for the correct terminology.

    See: http://dlang.org/phobos/std_numeric.html#.sumOfLog2s

    TODO: merge with `UsageOf`
   */
template packedBitSizeOf(T)
{
    static if (is(T == enum))
    {
        static assert(T.min != T.max, "enum T must have at least two enumerators");
        import core.bitop : bsr;
        enum range = T.max - T.min; // TODO: use uniqueEnumMembers.length instead?
        enum packedBitSizeOf = range.bsr + 1;
    }
    // TODO
    // else static if (isAggregate!T)
    // {
    //     foreach (E; T.tupleof)
    //     {
    //         ....;
    //     }
    // }
    else
    {
        enum packedBitSizeOf = 8*T.sizeof;
    }
}

@safe pure nothrow @nogc unittest
{
    static assert(packedBitSizeOf!ubyte == 8);
    static assert(!__traits(compiles,
                            {
                                enum E1 { x } static assert(packedBitSizeOf!E1 == 1);
                            }));
    enum E2 { x, y }
    static assert(packedBitSizeOf!E2 == 1);
    enum E3 { x, y, z }
    static assert(packedBitSizeOf!E3 == 2);
    enum E4 { x, y, z, w }
    static assert(packedBitSizeOf!E4 == 2);
    enum E5 { a, b, c, d, e }
    static assert(packedBitSizeOf!E5 == 3);
    enum E6 { a, b, c, d, e, f }
    static assert(packedBitSizeOf!E6 == 3);
    enum E7 { a, b, c, d, e, f, g }
    static assert(packedBitSizeOf!E7 == 3);
    enum E8 { a, b, c, d, e, f, g, h }
    static assert(packedBitSizeOf!E8 == 3);
    enum E9 { a, b, c, d, e, f, g, h, i }
    static assert(packedBitSizeOf!E9 == 4);
}


/+ Is the representation of `T.init` known at compile time to consist of nothing
 + but zero bits? Padding between a struct's fields is not considered.
 +/
template isInitAllZeroBits(T)
{
    static if (__traits(compiles, { enum _ = __traits(isZeroInit, T); }))
    {
        enum isInitAllZeroBits = __traits(isZeroInit, T);
        // pragma(msg, "TODO: use `enum isInitAllZeroBits = __traits(isZeroInit, T);` here and in `isAllZeroBits` and remove the test of isInitAllZeroBits");
    }
    else static if (T.sizeof == 0)
    {
        enum isInitAllZeroBits = true;
    }
    else
    {
        import std.traits : isStaticArray;
        static if (isStaticArray!T && __traits(compiles, T.init[0]))
        {
            enum isInitAllZeroBits = __traits(compiles, {
                    static assert(isAllZeroBits!(typeof(T.init[0]), T.init[0]));
                });
        }
        else
        {
            enum isInitAllZeroBits = __traits(compiles, {
                    static assert(isAllZeroBits!(T, T.init));
                });
        }
    }
}

@nogc nothrow pure @safe unittest
{
    static assert(isInitAllZeroBits!int);
    static assert(isInitAllZeroBits!(Object));
    static assert(isInitAllZeroBits!(void*));
    static assert(isInitAllZeroBits!uint);
    static assert(isInitAllZeroBits!(uint[2]));
    static assert(isInitAllZeroBits!(string));
    static assert(isInitAllZeroBits!(wstring));
    static assert(isInitAllZeroBits!(dstring));

    static assert(!isInitAllZeroBits!float);
    // static assert(isInitAllZeroBits!(float[0]));
    static assert(!isInitAllZeroBits!(float[2]));

    static struct S1
    {
        int a;
    }
    static assert(isInitAllZeroBits!S1);

    static struct S2
    {
        int a = 1;
    }
    static assert(!isInitAllZeroBits!S2);

    static struct S3
    {
        S1 a;
        int b;
    }
    static assert(isInitAllZeroBits!S3);
    static assert(isInitAllZeroBits!(S3[2]));

    static struct S4
    {
        S1 a;
        S2 b;
    }
    static assert(!isInitAllZeroBits!S4);

    static struct S5
    {
        real r = 0;
    }
    static assert(isInitAllZeroBits!S5);

    static struct S6
    {

    }
    static assert(isInitAllZeroBits!S6);

    static struct S7
    {
        float[0] a;
    }
    // TODO: static assert(isInitAllZeroBits!S7);

    static class C1
    {
        int a = 1;
    }
    static assert(isInitAllZeroBits!C1);

    // Ensure Tuple can be read.
    import std.typecons : Tuple;
    static assert(isInitAllZeroBits!(Tuple!(int, int)));
    static assert(!isInitAllZeroBits!(Tuple!(float, float)));

    // Ensure private fields of structs from other modules
    // are taken into account.
    import std.random : Mt19937;
    static assert(!isInitAllZeroBits!Mt19937);
    // Check that it works with const.
    static assert(isInitAllZeroBits!(const(Mt19937)) == isInitAllZeroBits!Mt19937);
    static assert(isInitAllZeroBits!(const(S5)) == isInitAllZeroBits!S5);
}

/+ Can the representation be determined at compile time to consist of nothing
 + but zero bits? Padding between a struct's fields is not considered.
 +/
template isAllZeroBits(T, T value)
{
    static if ((is(T == class) || is(T == typeof(null))) && // need this special case
               value is null)   // because pointer must be compared with `is` instead of `==` for `SSOString` case below
    {
        enum isAllZeroBits = true;
    }
    else static if (value == T.init && // NOTE `value is T.init` crashes compiler for `SSOString`
                    __traits(compiles, { enum _ = __traits(isZeroInit, T); }))
    {
        enum isAllZeroBits = __traits(isZeroInit, T);
    }
    else
    {
        // pragma(msg, "T: ", T.stringof, " value:", value);
        import std.traits : isDynamicArray, isStaticArray;
        static if (isDynamicArray!(T))
        {
            enum isAllZeroBits = value is null && value.length is 0;
        }
        else static if (is(typeof(value is null)))
        {
            enum isAllZeroBits = value is null;
        }
        else static if (is(typeof(value is 0)))
        {
            enum isAllZeroBits = value is 0;
        }
        else static if (isStaticArray!(T))
        {
            enum isAllZeroBits = ()
            {
                // Use index so this works when T.length is 0.
                static foreach (i; 0 .. T.length)
                {
                    if (!isAllZeroBits!(typeof(value[i]), value[i]))
                        return false;
                }
                return true;
            }();
        }
        else static if (is(T == struct) ||
                        is(T == union))
        {
            enum isAllZeroBits = ()
            {
                static foreach (e; value.tupleof)
                {
                    if (!isAllZeroBits!(typeof(e), e))
                        return false;
                }
                return true;
            }();
        }
        else
            enum isAllZeroBits = false;
    }
}

@nogc nothrow pure @safe unittest
{
    static assert(isAllZeroBits!(int, 0));
    static assert(!isAllZeroBits!(int, 1));

    import std.meta : AliasSeq;
    foreach (Float; AliasSeq!(float, double, real))
    {
        assert(isAllZeroBits!(Float, 0.0));
        assert(!isAllZeroBits!(Float, -0.0));
        assert(!isAllZeroBits!(Float, Float.nan));
    }

    static assert(isAllZeroBits!(void*, null));
    static assert(isAllZeroBits!(int*, null));
    static assert(isAllZeroBits!(Object, null));
}

/+ Can the representation be determined at compile time to consist of nothing
but 1 bits? This is reported as $(B false) for structs with padding between
their fields because `opEquals` and hashing may rely on those bits being zero.

Note:
A bool occupies 8 bits so `isAllOneBits!(bool, true) == false`

See_Also:
https://forum.dlang.org/post/hn11oh$1usk$1@digitalmars.com
https://github.com/dlang/phobos/pull/6024
+/
template isAllOneBits(T, T value)
{
    import std.traits : isIntegral, isSomeChar, Unsigned;
    static if (isIntegral!T || isSomeChar!T)
    {
        import core.bitop : popcnt;
        static if (T.min < T(0))
            enum isAllOneBits = popcnt(cast(Unsigned!T) value) == T.sizeof * 8;
        else
            enum isAllOneBits = popcnt(value) == T.sizeof * 8;
    }
    else static if (__traits(isStaticArray, typeof(value)))
    {
        enum isAllOneBits = ()
        {
            bool b = true;
            // Use index so this works when T.length is 0.
            static foreach (i; 0 .. T.length)
            {
                b &= isAllOneBits!(typeof(value[i]), value[i]);
                if (b == false)
                    return b;
            }

            return b;
        }();
    }
    else static if (is(typeof(value) == struct))
    {
        enum isAllOneBits = ()
        {
            bool b = true;
            size_t fieldSizeSum = 0;
            static foreach (e; value.tupleof)
            {
                b &= isAllOneBits!(typeof(e), e);
                if (b == false)
                    return b;
                fieldSizeSum += typeof(e).sizeof;
            }
            // If fieldSizeSum == T.sizeof then there can be no gaps
            // between fields.
            return b && fieldSizeSum == T.sizeof;
        }();
    }
    else
    {
        enum isAllOneBits = false;
    }
}

@nogc nothrow pure @safe unittest
{
    static assert(isAllOneBits!(char, 0xff));
    static assert(isAllOneBits!(wchar, 0xffff));
    static assert(isAllOneBits!(byte, cast(byte) 0xff));
    static assert(isAllOneBits!(int, 0xffff_ffff));
    static assert(isAllOneBits!(char[4], [0xff, 0xff, 0xff, 0xff]));

    static assert(!isAllOneBits!(bool, true));
    static assert(!isAllOneBits!(wchar, 0xff));
    static assert(!isAllOneBits!(Object, Object.init));
}

/+ Can the representation be determined at compile time to consist of nothing
but 1 bits? This is reported as $(B false) for structs with padding between
their fields because `opEquals` and hashing may rely on those bits being zero.

See_Also:
https://forum.dlang.org/post/hn11oh$1usk$1@digitalmars.com
https://github.com/dlang/phobos/pull/6024
+/
template isInitAllOneBits(T)
{
    static if (__traits(isStaticArray, T) && __traits(compiles, T.init[0]))
        enum isInitAllOneBits = __traits(compiles, {
            static assert(isAllOneBits!(typeof(T.init[0]), T.init[0]));
        });
    else
        enum isInitAllOneBits = __traits(compiles, {
            static assert(isAllOneBits!(T, T.init));
        });
}

@nogc nothrow pure @safe unittest
{
    static assert(isInitAllOneBits!char);
    static assert(isInitAllOneBits!wchar);
    static assert(!isInitAllOneBits!dchar);

    static assert(isInitAllOneBits!(char[4]));
    static assert(!isInitAllOneBits!(int[4]));
    static assert(!isInitAllOneBits!Object);

    static struct S1
    {
        char a;
        char b;
    }
    static assert(isInitAllOneBits!S1);

    static struct S2
    {
        char a = 1;
    }
    static assert(!isInitAllOneBits!S2);

    static struct S3
    {
        S1 a;
        char b;
    }
    static assert(isInitAllOneBits!S3);
    static assert(isInitAllOneBits!(S3[2]));

    static struct S4
    {
        S1 a;
        S2 b;
    }
    static assert(!isInitAllOneBits!S4);

    static struct Sshort
    {
        short r = cast(short)0xffff;
    }
    static assert(isInitAllOneBits!Sshort);

    static struct Sint
    {
        int r = 0xffff_ffff;
    }
    static assert(isInitAllOneBits!Sint);

    static struct Slong
    {
        long r = 0xffff_ffff_ffff_ffff;
    }
    static assert(isInitAllOneBits!Slong);

    // Verify that when there is padding between fields isInitAllOneBits is false.
    static struct S10
    {
        align(4) char a;
        align(4) char b;
    }
    static assert(!isInitAllOneBits!S10);

    static class C1
    {
        char c;
    }
    static assert(!isInitAllOneBits!C1);
}
